깊이 우선 검색(DFS)BFS와 직전원소 부분 그래프(predecessor subgraph)의 정의를 달리한다.
Gπ=(V+Eπ)
깊이 우선 검색의 직전 원소 부분 그래프는 여러개의 깊이 우선 트리로 구성된 깊이 우선 포리스트를 형성한다.
깊이 우선 검색에서는 color 대신 처음 발견되었을 때(GRAY) 시간 d, 주변 조사를 마쳤을 때(BLACK) 시간 f를 속성을 가짐
#include <iostream>
#include <queue>
#include <climits>
#include <chrono>
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NIL -1
using namespace std;
struct Node{
int value;
Node* next=nullptr;
Node(int _value): value(_value) {}
};
struct Vertex{
int color=WHITE, d=0, f=0, pi=NIL;
Vertex(){}
};
struct adjList{
Node** aL;
Vertex* vertex;
int vN, eN, t=0;
adjList(int _vN, int E[][2], int _eN): vN(_vN), eN(_eN){
vertex=new Vertex[this->vN];
aL=new Node*[this->vN];
for(int i=0; i<this->eN; ++i){
Node* nN1=new Node(E[i][1]);
if(aL[E[i][0]-1]==nullptr){
aL[E[i][0]-1]=nN1;
} else {
Node* tmp=aL[E[i][0]-1];
aL[E[i][0]-1]=nN1;
nN1->next=tmp;
}
}
}
void DFSvisit(int u){
this->t++;
this->vertex[u-1].d=this->t;
this->vertex[u-1].color=GRAY;
Node* cur=this->aL[u-1];
while(cur!=nullptr){
int v=cur->value;
if(vertex[v-1].color==WHITE){
this->vertex[v-1].pi=u;
DFSvisit(v);
}
cur=cur->next;
}
this->vertex[u-1].color=BLACK;
this->t++;
this->vertex[u-1].f=t;
}
void DFS(void){
for(int u=0; u<this->vN; ++u){
this->vertex[u].color=WHITE;
this->vertex[u].pi=NIL;
}
this->t=0;
for(int u=0; u<this->vN; ++u){
if(this->vertex[u].color==WHITE) DFSvisit(u+1);
}
}
};
int main(void){
int E[][2]={
{1, 2},
{2, 3},
{1, 3},
{3, 4},
{4, 2},
{5, 4},
{5, 6},
{6, 6}
};
adjList* graph=new adjList(6, E, 8);
graph->DFS();
return 0;
}
(u.d, u.f) & (v.d, v.f)는 아래 세가지 조건 중 하나를 만족한다.
- 겹치는 부분이 없다 == 깊이 우선 포레스트에서 둘 중에 다른 것의 자손이 아님
- u가 구간 v에 완전히 포함됨 == u는 깊이 우선 트리에서 v의 자손이다.
- v가 구간 u에 완전히 포함됨 == v는 깊이 우선 트리에서 u의 자손이다.
DFS의 직전원소 부분 그래프가 트리들의 포레스트를 형성하며,
발견 시간과 종료시간이 괄호구조를 가진다.
간선의 구분
- 트리 간선(Tree edge) ; WHITE
- 역행 간성(Back edge) ; GRAY
- 순행 간선(Forward edge) ; BLACK
- 교차 간선(Cross edge) ; BLACK
순행 & 교차 간선은 무방향 그래프의 깊이 우선 탐색에서는 발생할 수 없음
위상정렬(Topological Sort)
방향 비순환 그래프에서 간선 (u, v)에 대해서
u가 v보다 먼저 나타나도록 모든 정점을 선형을 나열
-> 깊이 우선 검색을 통해서 얻은 각 정적에 대한 f값을 역순으로 나열
강한 연결 요소(Strongly Connected Components)
GT=(V,ET)
- 각 정점의 f값을 얻기 위해 DFS(G)를 수행한다.
- G의 전치 행렬을 구한다.
- DFS(G^T)를 통해 얻은 f값을 역순으로 정렬